package main
import (
	"fmt"
)


type Node struct{
	key int
	value int
	pre *Node
	next *Node
}
type LRUCache struct {
	mp map[int]*Node   //通过map加速找到的速度
	cap int				//总共的容量
	len int				//实际的数量
	head *Node			//链表头
	tail *Node			//链表尾
}
//一般构造的都是双向循环链表


func Constructor(capacity int) LRUCache {
	return LRUCache{
		mp:make(map[int]*Node,capacity),
		cap:capacity,
		len: 0,
		head: nil,
		tail: nil,
	}
}
/*
将链表里的元素提升到第一位
*/
func (this *LRUCache) adjust2front(node *Node){
	//将多个地方的node取下来,接下来到头部
	//node在头部，直接返回
	if this.head==node{
		return
	}
	//node在结尾
	if this.tail==node{
		this.tail=node.pre
	}

	//node在中间
	if node.next!=nil{
		node.next.pre=node.pre
		if node.pre!=nil{
			node.pre.next=node.next			
		}
	}

	node.next=this.head
	this.head.pre=node
	this.head=node
}
/*
将最久未使用的元素删除
*/
func (this *LRUCache) Del(){
	if this.tail==nil{
		return
	}
	this.len--
	node:=this.tail
	delete(this.mp,node.key)
	if this.tail==this.head{	
		this.tail=nil
		this.head=nil	
		return
	}
	this.tail=node.pre
	this.tail.next=nil
}
/*
向链表里添加元素，添加到链表头
*/
func (this *LRUCache) Add(node *Node){
	this.len++
	if this.head==nil{ //链表为空
		this.head=node
		this.tail=node
		return
	}
	node.next=this.head
	this.head.pre=node
	this.head=node
}



func (this *LRUCache) Put(key int, value int)  {
	node,ok:=this.mp[key]
	if ok{
		//如果表中存在，那就将此节点移动到链表最前边
		node.value=value
		this.adjust2front(node)
	}else{
		if this.len==this.cap{
			//删除最后一个元素
			this.Del()
		}
		//将新元素加入到链表里
		node:=&Node{key,value,nil,nil}
		this.mp[key]=node
		this.Add(node)
	}
}

func (this *LRUCache) Get(key int) int {
	node,ok:=this.mp[key]
	if ok{
		this.adjust2front(node)
		return node.value
	}
	return -1
}


func LRU( operators [][]int ,  k int ) []int {
    // write code here
	ans:=make([]int,0)
	cache:=Constructor(k)
	for _,item:=range operators{
		if item[0]==1{
			cache.Put(item[1],item[2])
		}else{
			ans=append(ans,cache.Get(item[1]))
		}
	}
    return ans
}

func main(){
	t:=[][]int{
		[]int{1,1,1},
		[]int{1,2,2},
		[]int{1,3,2},
		[]int{2,1},
		[]int{1,4,4},
		[]int{2,2},
	}
	fmt.Printf("%v\n",LRU(t,3))

}
